The present invention relates generally to matched filters for digitally coded signals and, more particularly, to a matched filter using precomputation to reduce power consumption in radio receivers of Code Division Multiple Access (CDMA) signals.
The cellular telephone industry has made phenomenal strides in commercial operations in the United States as well as the rest of the world. Growth in major metropolitan areas has far exceeded expectations and is outstripping system capacity. If this trend continues, the effects of rapid growth will soon reach even the smallest markets. Innovative solutions are required to meet these increasing capacity needs as well as maintain high quality service and avoid rising prices.
Throughout the world, one important step in cellular systems is to change from analog to digital transmission. Equally important is the choice of an effective digital transmission scheme for implementing the next generation of cellular technology. Furthermore, it is widely believed that the first generation of Personal Communication Networks (PCNs) employing low cost, pocket-size, cordless telephones that can be carried comfortably and used to make or receive calls in the home, office, street, car, etc. will be provided by cellular carriers using the next generation of digital cellular system infrastructure and cellular frequencies. The key feature demanded of these new systems is increased traffic capacity.
Currently, channel access is achieved using Frequency Division Multiple Access (FDMA), Time Division Multiple Access (TDMA), and Code Division Multiple Access (CDMA) methods. In FDMA systems, a communication channel is a single radio frequency band into which a signal""s transmission power is concentrated. Interference with adjacent channels is limited by the use of bandpass filters that only pass signal energy within the filters"" specified frequency bands. Thus, with each channel being assigned a different frequency, system capacity is limited by the available frequencies as well as by limitations imposed by channel reuse.
In TDMA systems, a channel consists of a time slot in a periodic train of time intervals over the same frequency. Each period of time slots is called a frame. A given signal""s energy is confined to one of these time slots. Adjacent channel interference is limited by the use of a time gate or other synchronization element that only passes signal energy received at the proper time. Thus, the problem of interference from different relative signal strength levels is reduced.
Capacity in a TDMA system is increased by compressing the transmission signal into a shorter time slot. As a result, the information must be transmitted at a correspondingly faster burst rate that increases the amount of occupied spectrum proportionally.
With FDMA or TDMA systems or hybrid FDMA/TDMA systems, the goal is to ensure that two potentially interfering signals do not occupy the same frequency at the same time. In contrast, CDMA systems allow signals to overlap in both time and frequency. Thus, all CDMA signals share the same frequency spectrum. In both the frequency and the time domain, the multiple access signals overlap. Various aspects of CDMA communications are described, for example, in xe2x80x9cOn the Capacity of a Cellular CDMA System,xe2x80x9d by Gilhousen, Jacobs, Viterbi, Weaver and Wheatley, IEEE Trans. On Vehicular Technology, May 1991.
In a typical CDMA system, the informational data stream to be transmitted is impressed upon a much higher bit rate data stream generated by a pseudo-random noise code (PNcode) generator. The informational data stream and the higher bit rate code data stream are typically multiplied together. This combination of the lower-bit rate informational data stream with the higher bit rate code data stream is called coding or spreading the informational data stream signal. Each informational data stream or channel is allocated a unique spreading code. A plurality of coded information signals are transmitted on radio frequency carrier waves and jointly received as a composite signal at a receiver. Each of the coded signals overlaps all of the other coded signals, as well as noise-related signals, in both frequency and time. By correlating the composite signal with one of the unique spreading codes, the corresponding information signal is isolated and decoded.
There are a number of advantages associated with CDMA communication techniques. The capacity limits of CDMA-based cellular systems are projected to be up to twenty times that of existing analog technology as a result of the wideband CDMA system""s properties such as improved coding gain/modulation density, voice activity gating, sectorization and reuse of the same spectrum in every cell. CDMA is virtually immune to multi-path interference, and eliminates fading and static to enhance performance in urban areas. CDMA transmission of voice by a high bit rate encoder ensures superior, realistic voice quality. CDMA also provides for variable data rates allowing many different grades of voice quality to be offered. The scrambled signal format of CDMA eliminates cross-talk and makes it very difficult and costly to eavesdrop or track calls, insuring greater privacy for callers and greater immunity from air-time fraud. In communication systems following the CDMA or xe2x80x9cspread spectrumxe2x80x9d concept, the frequency spectrum of an informational data stream is spread using a code uncorrelated with that of the data signals. The codes are also unique to every user. This is the reason why a receiver that has knowledge about the code of the intended transmitter is capable of selecting the desired signal.
There are several different techniques to spread a signal. Two of the most popular are Direct-Sequence (DS) and Frequency-Hopping (FH), both of which are well known in the art. According to the DS technique, the data signal is multiplied by an uncorrelated pseudo-random code (i.e., the previously described PNcode). The PNcode is a sequence of chips (bits) valued at xe2x88x921 and 1 (polar) or 0 and 1 (non-polar) and has noise like properties. One way to create a PNcode is by means of at least one shift register. When the length of such a shift register is N, the period, TDS, is given by the equation TDS=2Nxe2x88x921.
In a receiver in a CDMA system, the received signal is multiplied again by the same (synchronized) PNcode. Since the code consists of +1""s and xe2x88x921""s (polar), this operation removes the code from the signal and the original data signal is left. In other words, the despreading operation is the same as the spreading operation.
Referring to FIG. 1, there is shown a schematic diagram of a prior art correlator 10 which is used to compute correlations between the last M signal samples received and an M-bit codeword. An M-element delay line 11 stores received signal samples and sequentially shifts them through each of the M stages. Consequently, the delay line memory elements contain the last M signal sample values received. After each new signal sample is shifted in and each old signal sample is shifted out, the M signal sample values are read out of the delay line into M sign-changers 13, where the M signal sample values are multiplied by +1 or xe2x88x921 according to the bits b1 . . . bM of a predetermined code stored in code store 12 with which correlation is to be computed. The sign-changed values are then summed in adder 14 to produce a correlation result.
In general, the process of correlating an M-element vector A=(a1, a2 . . . aM) with an M-element vector B=(b1,b2 . . . bM) involves forming the inner product Axc2x7B=a1xc2x7b1+a2xc2x7b2+ . . . aMxc2x7bM. When the elements of one of the vectors (e.g., B) comprises only binary values (arithmetically +1 or xe2x88x921), the products such as a1xc2x7b1 simplify to xc2x1a1, but the process of adding the M values xc2x1a1,xc2x1a2, . . . xc2x1aM is still a significant effort when it has to be performed for every new value of xe2x80x9caxe2x80x9d received.
The prior art includes many variations of the correlator 10 shown in FIG. 1. For example, signal samples may be single-bit or xe2x80x9chard-limitedxe2x80x9d quantities of only +1 or xe2x88x921 instead of multi-bit quantities. The sign-changers 13 used then are typically simple XOR gates. In that case, the adder 14 may first add pairs of single-bit values to obtain M/2 two-bit values; M/4 two-bit adders then add two-bit values to obtain M/4 three-bit values, and so on. Such a structure, known as an xe2x80x9cadder treexe2x80x9d, is simpler when the input values are single-bit rather than multi-bit values.
For single-bit value signal samples, the adder tree can be replaced by an up/down counter that scans the M values, and counts up when a +1 is encountered and down when a xe2x88x921 is encountered. Likewise, for multi-bit value signal samples, a parallel adder tree can be replaced by a sequential adder that extracts each of the M values, in turn, from the delay line memory and adds it to an accumulator. In the latter case, the logic employed must operate M-times as fast as in the parallel adder case. Consequently, there is a trade-off between the overall speed of the correlator and the logic complexity. Nevertheless, in each of the above-described prior art correlator variations, it is necessary to combine M values anew after each new signal sample is received. This can result in large amounts of power being consumed, particularly when the power supply is a portable supply such as a battery.
Referring to FIG. 2, there is shown a schematic diagram of another prior art correlator 20, this one having an address counter 21, a switch matrix 22, a plurality of stores 23, a corresponding plurality of sign-changers 24, and an adder tree 25. Each new signal sample, S(i), is input to a first stage 22a of the switch matrix 22 that is controlled by the address counter 21 to steer the input value of the signal sample to the next available one of stores 23, which will be the store that was last used xe2x80x9cnxe2x80x9d samples previously to store sample S(ixe2x88x92n). Sample S(ixe2x88x92n) is thus overwritten by the new sample S(i). The purpose of the switch matrix 22 is to connect the input sample lines only to the store selected by the address counter 21 in order, to reduce the capacitive loading on the input lines, and thereby reduce power consumption when operating at a high sample rate. The first stage 22a of the switch matrix 22 is controlled by a first bit of the address counter 21 to steer the input value either to a first of the second stage switches 22b or to a second of the second stage switches 22b. A second bit of the address counter 21 operates the second stage switches to steer the input value to one of four third stage switches 22c, and so forth, until a final stage of switches 22d steers the input value to a unique one of stores 23. The first address counter bit used to control switch 22a is preferably the most rapidly changing address counter bit, while the more numerous switches in the final stage of switches 22d are preferably controlled by the most slowly varying bit of the address counter 21, thereby minimizing the power consumption associated with toggling switches. By this means, the stores 23 memorize the last xe2x80x9cnxe2x80x9d input sample values, where xe2x80x9cnxe2x80x9d is a power of two in this example. Of course, xe2x80x9cnxe2x80x9d can also be less than a power of two and the address counter 21 can be arranged to count from 0 to nxe2x88x921 and then reset to zero. Since only one store value is modified at each sample clock instant, the power consumption of this arrangement is much lower than shifting the input values through an xe2x80x9cnxe2x80x9d-stage shift register, where all xe2x80x9cnxe2x80x9d values would change at each sample clock instant, such as in the correlator 10 of FIG. 1. The difference is that, in the shift register case, the first register always contains the most recent signal sample, S(i). In the correlator 20 of FIG. 2, however, the store that contains the most recent signal sample, S(i), rotates cyclically as xe2x80x9cixe2x80x9d increments, but is nevertheless indicated by the value of the address counter 21.
The correlation to be computed is given by the expression,
Cnxc2x7S(i)+C(nxe2x88x921)xc2x7S(ixe2x88x921)+C(nxe2x88x922)xc2x7S(ixe2x88x922) . . . +C(1)xc2x7S(ixc2x7n+1)xe2x80x83xe2x80x83(1)
where (C1,C2,C3 . . . C(n)) is an n-bit code with each code bit having a value of +1 or xe2x88x921. Multiplications by +1 or xe2x88x921 are simply performed by either changing the sign (for xe2x88x921) or not (for +1) using the sign-changers 24 controlled by the respective code bit. The code bits are supplied by a code generator (not shown) that must rotate the code such that Cn is applied to the multiplier in the sign-changer 24 that is connected to the store 23 containing the most recent signal sample S(i), which is indicated by the address counter 21. Since the code comprises single bit values, it is preferable to rotate the code rather than rotate the contents of stores 23, which hold multi-bit signal samples.
The sign-changed outputs from the sign-changer 24 are added in the adder tree 25, which adds pairs at a time. The number of stages of the adder tree 25 that are required to produce the final correlation value output is the same as the number of switch stages 22a . . . 22d needed to address a unique one of stores 23 (i.e., LOG2(n) stages). Thus, a 64-bit correlator comprises sixty-four stores 23, six stages of input steering switches 22, and six stages of adder tree 25 totaling 32+16+8+4+2+1=63 adders.
Although the input steering arrangement in the correlator 20 of FIG. 2 gives significant power economies compared to a shift register, the number of additions per correlation value computed is still equal to 63. That is, the number of additions has not been reduced through the use of the correlator 20 of FIG. 2. Thus, similar to the correlator 10 of FIG. 1, the number of additions required in the correlator 20 of FIG. 2 can result in large amounts of power being consumed, particularly when the power supply is a portable supply such as a battery.
In view of the foregoing, it would be desirable to provide a matched filter that minimizes computations so as to reduce power consumption.
According to the present invention, a technique for correlating a sequence of signal sample values with a predetermined digital code to produce correlation values for shifts in the sequence of signal sample values relative to the predetermined digital code is provided. In one embodiment, the technique is realized by combining subgroups of the signal sample values in the sequence to form sets of precombinations, and then selecting one precombination from each set of precombinations to provide a plurality of selected precombinations. The plurality of selected precombinations are then added or subtracted to produce a correlation value corresponding to a shift in the sequence of signal sample values.
The predetermined digital code is typically a segment of a direct-sequence spread-spectrum spreading code. The predetermined digital code can be a real code, and the signal sample values can be real values. Alternatively, the predetermined digital code can comprise a real code and an imaginary code, and the signal sample values can be complex values.
In accordance with other aspects of the present invention, the sets of precombinations are formed from sums and differences of pairs of the signal sample values. The sets of precombinations can be formed from sums and differences of pairs of real or pairs of imaginary signal sample values. In such a case, the sets of precombinations are preferably formed from a sum and a difference of the real part of one signal sample value and the imaginary part of another signal sample value.
In accordance with further aspects of the present invention, the sets of precombinations are formed from all possible combinations of sums and differences of a given number of the signal sample values. In such a case, only one sign polarity is beneficially used with one of the signal sample values, thereby halving the number of precombinations formed in each set of precombinations.
In accordance with still further aspects of the present invention, pairs of precombinations are beneficially combined from an oldest set of precombinations to delete the contribution of an oldest one of the signal sample values in the oldest set of precombinations, the result is then combined with a newest signal sample value to produce an updated set of precombinations. Preferably, the updated set of precombinations is produced each time a new signal sample value is received, and the updated set of precombinations overwrites the oldest set of precombinations in the storage device. The oldest set of precombinations is the set of precombinations that depends upon the oldest signal sample value the contribution of which has not yet been deleted.
In accordance with still further aspects of the present invention, the sets of precombinations are preferably stored after they are formed. The sets of precombinations are typically stored in a storage device, which is preferably a circular buffer. The storage device beneficially includes a routing switch tree for routing a set of precombinations to a designated set of storage elements. Such a routing switch tree is preferably a binary tree comprising a number of stages equal to the logarithm to the base two of the number of storage locations for sets of precombinations. A stage of the binary routing switch tree having a smaller number of switch elements preferably switches route more frequently than a stage having a greater number of switch elements. Preferably, the storage device stores the sets of precombinations in an order which is bit-reversed relative to the time-sequential order of their formation.
In accordance with still further aspects of the present invention, the selection of the precombinations is preferably controlled by a corresponding sub-group of bits of the predetermined digital code, and each selected precombination is then preferably added or subtracted according to the polarity of one of the bits of the corresponding subgroup of bits. Each selected precombination is beneficially multiplied with a corresponding preselected bit from the predetermined digital code to change or affirm the polarity of each selected precombination.
In accordance with still further aspects of the present invention, the predetermined digital code comprises a first number of code symbols and the sets of precombinations are formed of a subgroup containing a second number of signal sample values not divisible into the first number. The present invention can then be realized as a matched filter comprising a correlator for correlating with a predetermined code of a length that is divisible by the second number.